UVa/11504 - Dominos/11504.3.cpp

   1 /*
   2   Problem: 11504 - Dominos
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Accepted
   7  */
   8
   9 using namespace std;
  10 #include <iostream>
  11 #include <deque>
  12 #include <vector>
  13 #include <cassert>
  14 #include <set>
  15
  16 const int N = 100005;
  17
  18 vector<int> g[N], gt[N];
  19 int visited[N], scc[N], in_degree[N];
  20
  21 void dfs(int u, int mark, deque<int> *in_order, int visited[], vector<int> g[]){
  22   visited[u] = mark;
  23
  24   vector<int> &out = g[u];
  25   for (int k=0, m=out.size(); k<m; ++k){
  26     int v = out[k];
  27     if (!visited[v]) dfs(v, mark, in_order, visited, g);
  28   }
  29   if (in_order) in_order->push_front(u);
  30 }
  31
  32 int main(){
  33   int t;
  34   for(cin >> t; t--;){
  35     int n, m; cin >> n >> m;
  36
  37     for (int i=0; i<=n; ++i) g[i].clear(), gt[i].clear(), visited[i] = scc[i] = in_degree[i] = 0;
  38
  39     for (int u, v, i=0; i<m && cin >> u >> v; ++i) g[u].push_back(v), gt[v].push_back(u);
  40
  41     deque<int> in_order;
  42
  43     for (int i=1; i<=n; ++i)
  44       if (!visited[i])
  45         dfs(i, 1, &in_order, visited, g);
  46
  47
  48     int id = 1;
  49     for (deque<int>::iterator i=in_order.begin(); i!=in_order.end(); ++i)
  50       if (!scc[*i])
  51         dfs(*i, id++, NULL, scc, gt);
  52
  53
  54     /*
  55     for (int i=0; i<=n; ++i){
  56       printf("ssc[%d] = %d\n", i, scc[i]);
  57     }
  58     cout << endl;
  59     */
  60
  61
  62     for (int i=1; i<=n; ++i){
  63       vector<int> &out = g[i];
  64       for (int k=0, m=out.size(); k<m; ++k){
  65         int j = out[k];
  66         if (scc[i] != scc[j]) in_degree[scc[j]]++;
  67       }
  68     }
  69
  70     int ans = 0;
  71     for (int i=1; i<id; ++i){
  72       //printf("in_degree[%d] = %d\n", i, in_degree[i]);
  73       ans += !in_degree[i];
  74     }
  75
  76     cout << ans << endl;
  77   }
  78   return 0;
  79 }
  80
  81
  82 /*
  83   Explicación del algoritmo:
  84
  85   Lo primero es ver que cada componente fuertemente conexa del grafo puede
  86   tumbarse completamente usando solo una ficha. Entonces primero reducimos
  87   el grafo a un DAG donde cada nodo representa una componente fuertemente
  88   conexa del grafo original.
  89
  90   La respuesta es el número de nodos en el nuevo grafo que tienen in-degree == 0.
  91  */